package oj_leetcode;

import java.util.Arrays;

public class SortColors {

    public void sortColors(int[] nums) {
        int[] exist = new int[3];
        int[] order = new int[3];
        for (int i = 0; i < 3; i++) {
            order[i] = i;
        }
        sortColors(nums, exist, 0, order);
    }

    public void sortColors(int[] nums, int[] exists, int index, int[] order) {
        if (index == nums.length) {
            return;
        }
        int number = nums[index];
        if (exists[number] == 0) {
            for (int i = 0; i < 3; i++) {
                // important for delete the last element of some cate in swap step
                if (order[i] == number) {
                    break;
                }
                if (order[i] == -1) {
                    order[i] = number;
                    break;
                }
            }
        }

        int offset = 0;
        int i = 0; // order
        for (; i < 3; i++) {
            offset += exists[order[i]];
            if (order[i] == number) {
                break;
            }
        }
        if (offset == index) {
            exists[number] += 1;
            index++;
        } else {
            swap(nums, offset, index);
            exists[nums[index]] -= 1;
            exists[number] += 1;
        }

        sortColors(nums, exists, index, order);

    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public static void main(String[] args) {
        int[] res = new int[]{2, 0, 2, 1, 1, 0};
        new SortColors().sortColors(res);
        System.out.println(Arrays.toString(res));
    }

}
